"""
        给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），
        并使这些整数的乘积最大化。
        返回 你可以获得的最大乘积 。

        示例 1:
                输入: n = 2
                输出: 1
                解释: 2 = 1 + 1, 1 × 1 = 1。
        示例 2:
                输入: n = 10
                输出: 36
                解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
"""


class Solution:
    """
    1：理解dp数组的含义，保存第i的数的拆分乘积最大
    2：初始化dp数组，0没有意义，故赋值为0，1不能拆分，保存自己,用于后面的调用
    3：确定状态转移方程，dp[i] = max(dp[i-j]*j,j*(i-j),dp[i])
    4：解释状态转移方程，dp[i]有两条路径，
       一条是拆分成两个数，
       一条是拆分成多个数，一个数遍历所有的拆分可能
       dp[]前面保存着如果这样拆，拆出数的最大乘
    """

    def integerBreak(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[2] = 1
        dp[1] = 1
        for i in range(3, n + 1):
            for j in range(1, i):
                dp[i] = max(dp[i - j] * j, j * (i - j), dp[i])
        return dp[-1]
